\n",
"\n",
"Note. This chapter will be mainly based on Chapter 1 of An Introduction to Numerical Analysis by Süli, Mayers. These notes are mainly a record of what we discussed and are not a substitute for attending the lectures and reading books! If anything is unclear/wrong, let me know and I will update the notes.\n",
"
\n",
"\n",
"Note: \n",
"These notes contain some (but not all) of the content of the lecture. Please let me know if there are any additions that you feel are particularly important and let me know if you find any errors. \n",
"
⚠ Subtractive cancellation \n",
"\n",
"When adding or subtracting numbers so that the result is much smaller in magnitude. \n",
"\n",
"Example 1: We know $x = -1.0000000000000000000147$ to $23$ significant digits but $x + 1 = -1.47 \\times 10^{-20}$ to only $3$ significant digits \n",
"\n",
"Example 2: Quadratic formula when $-b \\approx \\pm \\sqrt{b^2-4ac}$ \n",
"\n",
"Example 3: $f(x) = \\frac{e^x - 1}{x}$ vs $p(x) = 1 + \\frac{x}{2!} + \\frac{x^2}{3!} + \\dots + \\frac{x^8}{9!}$\n",
"\n",
"...\n",
"
Definition. \n",
"\n",
"If the condition number is large, we say the problem is *ill-conditioned* or the problem is badly conditioned \n",
"When the error can not be explained by an ill-conditioned problem, we will say the algorithm is *unstable*.
"
]
},
{
"cell_type": "markdown",
"id": "a46bc6c8",
"metadata": {},
"source": [
"## Chapter 2\n",
"\n",
"* Aim: for $f: [a,b] \\to \\mathbb R$, solve $f(\\xi) = 0$ for $\\xi \\in \\mathbb R$, \n",
"* Also, can find $\\xi$ such that $f(\\xi) = c$ (by considering $x \\mapsto f(x) - c$) or stationary points (by considering $f = F'$),\n",
"* Change of sign theorem. Converse is not true\n",
"* Can rewrite as $g(x) = x$ (in multiple ways)\n",
"* Brouwer's fixed point theorem"
]
},
{
"cell_type": "markdown",
"id": "02cd7482",
"metadata": {},
"source": [
"
Example. \n",
"\n",
"Solve $f(x) = x$ where $f(x) := e^x - 2x - 1$. \n",
"Apply change of sign theorem to $f$ to conclude there exists $\\xi \\in [1,2]$ such that $f(\\xi) = 0$.\n",
"
\n",
"\n",
"Here, we see that $x_n \\to \\xi \\approx 1.26 \\in [1,2]$ but $y_{n} \\to 0$ so the formulations $g(x) = x$ and $h(x) = x$ are equivalent, but they lead to different numerical methods.\n",
"
Definition. \n",
"\n",
"Let $(x_n) \\to \\xi$. Suppose that there exist $\\alpha\\geq1$ and $\\mu \\geq 0$ such that\n",
"\n",
"\\begin{align}\n",
" \\lim_{n\\to\\infty} \\frac{\\left|x_{n+1} - \\xi\\right|}{\\left|x_n - \\xi\\right|^\\alpha} = \\mu\n",
"\\end{align}\n",
"\n",
"* If $\\alpha = 1$ and $\\mu \\in (0,1)$, we say the convergence is *linear*,\n",
"* If $\\alpha = 1$ but $\\mu = 0$, we say the convergence is *superlinear* (i.e. faster than linear),\n",
"* If $\\alpha = 1$ and $\\mu = 1$, we say the convergence is *sublinear* (i.e slower than linear),\n",
"* If $\\alpha = 2$, we say the convergence is *quadratic*,...\n",
"\n",
"In the case where *(i)* $\\alpha = 1, \\mu \\in (0,1)$ or *(ii)* $\\alpha>1, \\mu> 0$, we say\n",
"* $(x_n) \\to \\xi$ with *order* $\\alpha$, \n",
"* $\\mu$ is the *asymptotic error constant*, and\n",
"* $\\rho := - \\log_{10} \\mu$ is the *asymptotic rate of convergence*.\n",
"\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "8ba2e2cc",
"metadata": {},
"source": [
"* Define the errors $e_n \\coloneqq |x_{n}-\\xi|$. Then, we have $e_{n+1} \\approx \\mu e_{n}^\\alpha$,\n",
"* For linear convergence, $e_{n+N} \\approx \\mu^n e_N = 10^{-\\rho n} e_N$ and so $\\rho$ measures the number of decimal digits of accuracy gained in one iteration (for sufficiently large $N$)\n",
"\n",
"
Example (cont.). \n",
"\n",
"Let's go back to our example: $f(x) = e^x - 2x - 1$. We have defined $g(x) = \\log( 2x + 1 )$ and we are trying to solve the fixed point problem $g(x) = x$ (which is mathematically equivalent to $f(x) = 0$).\n",
"\n",
"We have seen (numerically) that $x_{n+1} = g(x_n)$ with $x_1>0$ converges to $\\xi = g(\\xi) \\approx 1.26$. What is the order of convergence? What is the asymptotic error constant? Asymptotic rate of convergence?\n",
"
\n",
"\n",
"This quantity appears to converge to $\\mu \\in (0,1)$. Therefore, we have $(x_n) \\to \\xi$ linearly with asymptotic error constant $\\mu$ and asymptotic rate of convergence $\\rho$ where these constants are as follows:\n",
"\n",
"
\n",
"\n",
"Next: we will now prove (mathematically) that $x_{n+1} = g(x_n)$ converges linearly with $\\mu = |g'(\\xi)|$. Our computed value of $\\mu$ (after $15$ iterations) is close to this theoretical value: \n",
"\n",
"
Contraction Mapping Theorem (Banach fixed point theorem). \n",
"\n",
"Suppose $g:[a,b] \\to[a,b]$ is a contraction. Then, there exists a unique fixed point $\\xi = g(\\xi) \\in [a,b]$. Moreover, the iteration $x_{n+1} = g(x_n)$ converges to $\\xi$ for all $x_1 \\in [a,b]$\n",
"\n",
"
Remark. \n",
"\n",
"Notice that, by the mean value theorem, there exists $\\eta_n$ between $x_{n}$ and $\\xi$ for which \n",
"\n",
"\\begin{align}\n",
" \\frac\n",
" {|x_{n+1} - \\xi|}\n",
" {|x_n - \\xi|}\n",
" %\n",
" &= \\frac\n",
" {|g(x_n) - g(\\xi)|}\n",
" {|x_n - \\xi|} \\nonumber\\\\\n",
" %\n",
" &= \\frac\n",
" {|g'(\\eta_n)| |x_n - \\xi|}\n",
" {|x_n - \\xi|} \\nonumber\\\\\n",
" %\n",
" &= |g'(\\eta_n)|.\n",
"\\end{align}\n",
"\n",
"Therefore, since $(x_n) \\to \\xi$, and $\\eta_n$ is between $x_n$ and $\\xi$, we have \n",
"\n",
"\\begin{align}\n",
" \\lim_{n\\to\\infty}\n",
" \\frac\n",
" {|x_{n+1} - \\xi|}\n",
" {|x_n - \\xi|}\n",
" %\n",
" &= |g'(\\xi)|\n",
"\\end{align}\n",
"\n",
"and the order of convergence is at least linear with asymptotic error constant $\\mu = |g'(\\xi)|$. \n",
"\n",
"(Recal that, if $\\mu = 0$, the order of convergence is superlinear)\n",
"\n",
"
Example (cont.). \n",
"\n",
"Show that $g(x) = \\log( 2x + 1 )$ is a contraction on $[1,2]$ with $L = 2/3$. \n",
"Therefore $x_{n+1} = g(x_n)$ converges for all $x_1 \\in [1,2]$.\n",
"\n",
"\n",
"Answer: $g' \\in [\\frac23, \\frac25]$ on $[1,2]$ and so $g$ is a contraction with constant $L = \\frac23$. Applying the contraction mapping theorem shows that $(x_n) \\to \\xi$ in this case.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "b891928d",
"metadata": {},
"source": [
"* How many iterations to guarantee an error of $ \\leq \\epsilon$?\n",
"\n",
"Recall that $|x_{n+1} - \\xi| \\leq L |x_{n} - \\xi|$. In particular, we have $|x_1 - \\xi| \\leq |x_1 - x_2| + |x_2 - \\xi| \\leq |x_1 - x_2| + L|x_1-\\xi|$ and thus $|x_1 - \\xi| \\leq \\frac1{1-L} |x_1 - x_2|$. As a result, we have \n",
"\n",
"\\begin{align}\n",
" |x_{n+1} - \\xi| &\\leq L^n |x_1 - \\xi| \\nonumber\\\\\n",
" &\\leq \n",
" \\frac\n",
" {L^n}\n",
" {1-L} \n",
" |x_1 - x_2|\n",
"\\end{align}\n",
"\n",
"This number is less than $\\epsilon$ when\n",
"\n",
"\\begin{align}\n",
" n \\geq \\frac{ \\log \\frac{|x_1-x_2|}{\\epsilon(1-L)} }{\\log\\frac1L}.\n",
"\\end{align}\n",
"\n",
"This gives an upper bound on the number of iterations needed in order to be within some fixed tolerance.\n",
"\n",
"
Example. \n",
"\n",
"Back to $f(x) = e^x - 2x - 1$ written as the fixed point problem $g(x) = x$. For an error of $\\epsilon = 10^{-10}$, we require around $54$ iterations. Actually, $40$ will do (but we have an upper bound): \n",
"
Definition. \n",
"\n",
"$\\xi$ is a *stable fixed point of $g$* if the iteration $x_{n+1} = g(x_n)$ converges to $\\xi$ for all $x_1$ sufficiently close to $\\xi$ \n",
"$\\xi$ is an *unstable fixed point of $h$* if for all $\\delta > 0$ there exists $x_1 \\in [\\xi-\\delta, \\xi+\\delta]$ for which $x_{n+1} = g(x_n)$ does not converge to $\\xi$.\n",
"\n",
"
Example (cont.). \n",
"\n",
"$\\xi = 1.26...$ is a stable fixed point of $g(x) = \\log( 2x + 1 )$. \n",
"Proof: contraction mapping theorem on $[1,2]$\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "dd725c3f",
"metadata": {},
"source": [
"* Theorem: Suppose $h(\\xi) = \\xi$ and $h'$ is continuous with $|h'| > L > 1$ near $\\xi$. Then, $x_{n+1} = h(x_n)$ does not converge to $\\xi$ for all $x_1 \\not= \\xi$. "
]
},
{
"cell_type": "markdown",
"id": "52c2225b",
"metadata": {},
"source": [
"
Proof. \n",
"\n",
"Let $I_\\delta = [\\xi-\\delta,\\xi+\\delta]$ be such that $|g'| > L$ on $I_{\\delta}$. If $x_n \\in I_{\\delta}$ then there exists $\\eta \\in I_\\delta$ such that\n",
"\n",
"\\begin{align}\n",
" |x_{n+1} - \\xi| &= |h(x_{n}) - h(\\xi)| \\nonumber\\\\\n",
" %\n",
" &= |h'(\\eta)| |x_n - \\xi| \\nonumber\\\\\n",
" %\n",
" &> L |x_{n} - \\xi|.\n",
"\\end{align}\n",
"\n",
"Similarly, if $x_{n+1} \\in I_\\delta$, then $|x_{n+2} - \\xi| > L^2|x_{n} - \\xi|$. Since, $L> 1$ (and so $L^n\\to\\infty$ and $n\\to\\infty$), there exists $N$ such that $x_{n+N} \\not\\in I_{\\delta}$. \n",
"\n",
"We have therefore seen that if $x_n \\in I_\\delta$, there exists $N$ such that $x_{n+N} \\not\\in I_{\\delta}$. As a result, $(x_n)$ does not converge to $\\xi$. \n",
"\n",
"
Example (cont.). \n",
"\n",
"$\\xi = 1.26...$ is an unstable fixed point of $h(x) = \\frac{e^x -1}{2}$. In fact, for $x_1 > \\xi$, $x_{n+1}= h(x_n)$ diverges to infinity. \n",
"$\\zeta = 0$ is a stable fixed point of $h$. For $x_1 < \\log 2$, $x_{n+1}= h(x_n)$ converges to $0$. \n",
"